package com.github.yangyishe.p100;

import java.util.HashMap;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-interview-150
 * todo
 *
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 *
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 *
 * 示例 1：
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * 示例 2：
 *
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 解释：整个字符串 s 是最小覆盖子串。
 * 示例 3:
 *
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 *
 *
 * 提示：
 *
 * m == s.length
 * n == t.length
 * 1 <= m, n <= 105
 * s 和 t 由英文字母组成
 */
public class Problem76 {
    public static void main(String[] args) {
        String s="ADOBECODEBANC";
        String t="ABC";

        Problem76 problem76 = new Problem76();
        String minWindow = problem76.minWindow(s, t);
        System.out.println(minWindow);

    }

    /**
     * 思路:
     * t=>字符与需要出现此处的哈希表char2CountMap. 同时增加一个数字, 记录所有出现次数大于0的总数sumCount.
     * 同时创建另一个哈希表Map<Queue>:char2IndexQueue.记录出现的字符索引.出现相同的,就removeFirst
     * 遍历s的每一个字符串.
     * 1. 每出现一个哈希表中存在的字符, 则在哈希表中, 将该字符对应的数字减1.
     * 如果该操作导致count=0, 则sumCount-1
     * 如果出现sumCount=0, 则表示第一次出现覆盖子串, 记录出现索引minSonIndex为0, 同时记录子串长度minSonSize
     *
     *
     * 简化版思路:
     * 左右双指针(均为闭区间).
     * 1. 右侧移动, 到找到所有字符, 记录最小左索引和最小长度
     * 2. 左侧移动, 每到一个包含字符位, 均判断记录一次最小左索引和最小长度.
     *  直到找到最近一次关键字符位, 不满足要求. 再转为右侧移动.
     * 3. 以上移动, 直到右指针到头且左指针不满足位置.
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        Map<Character,Integer> char2CountMap=new HashMap<>();
        for(char c:t.toCharArray()){
            char2CountMap.putIfAbsent(c,0);
            char2CountMap.put(c,char2CountMap.get(c)+1);
        }
        int sumCount=char2CountMap.size();

        int minIndex=-1;
        int minSize=Integer.MAX_VALUE;

        // 表示覆盖子串的左索引(闭区间)->增加+探索
        int left=0;
        // 表示覆盖子串的右索引(闭区间)->减少+探索
        int right=0;
        while(right<s.length()){
            while(left<s.length()){
                if(sumCount!=0&&char2CountMap.containsKey(s.charAt(left))){
                    break;
                }
                char lc=s.charAt(left);
                if(char2CountMap.containsKey(lc)){
                    char2CountMap.put(lc,char2CountMap.get(lc)+1);
                    if(char2CountMap.get(lc)==1){
                        int newSize=right-left+1;
                        if(minSize>newSize){
                            minSize=newSize;
                            minIndex=left;
                        }
                        sumCount++;
                    }
                }

                left++;
            }

            if(right<left){
                right=left;
            }
            while(right<s.length()){
                char rc = s.charAt(right);
                if(char2CountMap.get(rc)!=null){
                    char2CountMap.put(rc,char2CountMap.get(rc)-1);
                    if(char2CountMap.get(rc)==0){
                        sumCount--;
                    }
                }
                if(sumCount==0){
                    int newSize=right-left+1;
                    if(minSize>newSize){
                        minSize=newSize;
                        minIndex=left;
                    }
                    break;
                }
                right++;
            }

        }

        return s.substring(minIndex,minIndex+minSize-1);
    }

    private Map<Character,Integer> char2CountMap=new HashMap<>();
    private int dealCharCount;

    private int minIndex=-1;
    private int minSize=Integer.MAX_VALUE;

    /**
     * 处理左侧.
     * 返回值表示是否还需要继续处理
     * @param s
     * @param left
     * @param right
     * @return
     */
    private boolean dealLeft(String s,int left,int right){
        char c = s.charAt(left);
        if(!char2CountMap.containsKey(c)){
            return true;
        }
        // 先判断当前是否合法
        if (isLegal(s,left,right)) {
            int size=right-left+1;
            if(minSize>size){
                minSize=size;
                minIndex=left;
            }
            // 之后的处理
            char2CountMap.put(c,char2CountMap.get(c)+1);
            if(char2CountMap.get(c)==1){
                dealCharCount--;
            }

            return true;
        }else{
            return false;
        }

    }

    /**
     * 处理右侧
     * 返回值表示是否还需要继续处理
     * @param s
     * @param left
     * @param right
     * @return
     */
    private boolean dealRight(String s,int left,int right){
        return false;
    }


    private boolean isLegal(String s,int left,int right){
        return dealCharCount==0;
    }


}
